The cloud computing model provides users an ubiquitous, convenient and on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services), that can be rapidly provisioned and released with minimal management effort or service-provider interaction. Cloud computing enables cloud services such as Computing as a Service wherein not only data storage but also computing is outsourced to the cloud. While from a business point of view cloud computing offers a lot of advantages, the non-transparent nature of the cloud may negatively affect the trust that users put in such systems wherein in this case users are not only users that consume the cloud services but also providers that want to exploit their products via the cloud.
For example, a software provider may want to exploit a program that comprises commercially sensitive information via the cloud. The commercially sensitive information may be implemented in a program as one or more values that are used in the processing of user input data. For example, an output of a program may be the result of a computation, e.g. a comparison, between commercially sensitive program data and privacy sensitive user input (e.g. financial, commercial, or medical data, passwords and/or biometric data or sensor data such as images of surveillance camera or data associated with a production process).
The output of the software program may be a result of one computation or several (different) computations. In the latter case, the output of a program may be represented as the result of the evaluation of a decision tree, which is evaluated in a linear way by going from the root of the tree downwards to one of the leaves. In each node a decision has to be made which path is taken to get closer to the leaves, (e.g. the end-points or end-labels), wherein the decision is the outcome of one or more computations, in particular a comparison between two values, and wherein each leaf represents a possible output of the program. A program that can be executed this way may be referred to as a linear branching program.
Linear branching programs may be found in simple software programs such as an Internet application or in more complex software programs including expert systems such as a medical or financial expert system. A medical expert system may determine the disease or fitness of a user on the basis of the personal medical data. Similarly, a financial expert system may assist a user in choosing the proper mortgage on the basis personal financial information of the user. Another application may be software fault diagnosis. A proper algorithm explaining the actual problem to the user on the basis of his personal error reports and giving him some advice may be commercially valuable.
In the above mentioned software programs, the sensitive program parameters may be considered as a valuable part or in some cases the most valuable part of the program, because these parameters are constructed on the basis of dedicated field expertise and/or numerous test runs. Outsourcing (part of) the storage and execution of such software program to a third party may expose commercially sensitive information to a third party. Similarly, when requesting execution of an outsourced program (e.g. a cloud application), a user may be required to send privacy sensitive user data to the cloud server thereby providing the cloud provider access to privacy sensitive information (or at least increasing the risk that privacy sensitive information can be accessed by third parties such as the cloud operator). For this reason, a software provider may be reluctant to outsource storage and execution of the program to the cloud. Similarly, a user may be reluctant to provide personal data to a program that is executed in the cloud. These security and privacy issues may seriously impede users and software providers to use cloud solutions and thereby blocking large-scale commercial applications of the cloud.
Barni et al. propose in their article “Privacy-Preserving ECG Classification With Branching Programs and Neural Networks”, IEEE transactions on information forensics and security, vol. 6, no. 2, 2011, a protocol between a server and a client wherein the server holds a linear branching program and the client holds user data. The protocol allows evaluation of a linear branching program on the basis of user data without disclosing the user data to the server and without disclosing the linear branching program to the (user of the) client. For each node a Garbled Circuit (GC) is made. The GCs are all communicated to the client for secure evaluation. This way, the user will not learn which attribute is compared with which threshold, and the server will not learn the value of the user attribute. At the end of the evaluation, the user may obtain an output representing in this particular case an ECG classification.
The protocol proposed by Barni et al. is designed for a two-party situation, i.e. a server and a client. This protocol cannot be straightforwardly extended to a three-party situation wherein the owner of a computer program outsources the exploitation of the program (e.g. storage and execution) to a third party without losing its security and privacy protecting properties.
The evaluation of the nodes by the user using Garbled Circuits requires a relatively large amount of traffic between the user and server and a relatively large processing power at the client side: in the scheme a final circuit calculates the classification on the basis of the outputs of all nodes, i.e. also the nodes that do not lie on the evaluation path from the root to the leaf. Hence, for the evaluation of large programs a large amount of processing power is required thereby not providing a solution that is scalable.
A further problem with the protocol proposed by Barni et al. is that the program is only computationally secure towards the user. Garbled circuits are used for secure evaluation of one pass linear circuits consisting of a number of Boolean gates, which are elementary operations on bits. Each gate is securely translated into a table where inputs and outputs are represented by keys, and the output keys are encrypted with input keys to assure that only one output (corresponding with the proper input values) can be obtained.
When sufficient computational power is available, such encryption scheme could be broken by a brute force attack. The output keys of each gate could be determined and the program would be revealed to the user, including the sensitive program parameters. The use of encryption during evaluation limits the security to computational security instead of the maximum achievable security, which is known as perfect security. In perfect security the user would never learn the sensitive program parameters even with infinite computing power.
Hence, there is a need in the art for improved methods and systems that enable secure computation of privacy sensitive user data by a software program. In particular, there is a need in the art for methods and systems that enable for secure computation of privacy sensitive user data by a software program wherein the storage and exploitation of the program is outsourced to a party that does not own the program.